import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {

    public List<List<Integer>> threeSum(int[] nums) {//三数之和
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; ) {
            if(nums[i] > 0) break;
            int left=i+1,right=n-1,target=-nums[i];
            while (left<right) {
                if(nums[left] + nums[right] < target) {
                    left++;
                }else if(nums[left] + nums[right] > target) {
                    right--;
                }else{
                    //ret.add(Arrays.asList(nums[i],nums[left],nums[right]));//asList:一次性传入多个元素
                    ret.add(List.of(nums[i],nums[right],nums[left]));//效果同上
                    left++;
                    right--;
                    while(left<right && nums[left] == nums[left-1]) left++;
                    while(left<right && nums[right] == nums[right+1]) right--;
                }
            }
            do
                i++;
            while (i < n && nums[i] == nums[i - 1]);
        }
        return ret;
    }


    public List<List<Integer>> fourSum(int[] nums, int target) {//四数之和
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n;) {
            for (int j = i+1; j < n; ) {
                //三数之和
                int left=j+1,right=n-1;
                int aim=target-nums[i]-nums[j];//求出两数之和
                while(left<right){
                    int sum=nums[left]+nums[right];
                    if(sum>aim){
                        right--;
                    }else if(sum<aim){
                        left++;
                    }else{
                        ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        left++;
                        right--;
                        while(left<right&&nums[left]==nums[left-1]) left++;//去重
                        while(left<right&&nums[right]==nums[right+1]) right--;//去重

                    }
                }
                j++;
                while(j<n&&nums[j]==nums[j-1])j++;//对j进行去重
            }
            i++;
            while(i<n&&nums[i]==nums[i-1])i++;
        }
        return ret;
    }
    public static void main(String[] args) {
        int[] nums={-1,0,1,2,-1,-4};
        Test test=new Test();
        System.out.println("三数字之和"+test.threeSum(nums));

        int[] nums2={1,0,-1,0,-2,2};
        Test test2=new Test();
        System.out.println("四数之和"+test2.fourSum(nums2, 0));
    }
}
